package book;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 树节点类
class TreeNode {
    final int number; // 编号
    final int value; // 节点值
    final List<TreeNode> children; // 子节点
    public TreeNode(int num, int val) {
        number = num;
        value = val;
        children = new ArrayList<>();
    }
}

class TreeSearchSolution {

    // 在树中寻找深度最小的目标节点
    // 并返回其编号
    int findNode(TreeNode root, int t) {
        // 使用一个队列保存待搜索的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // BFS搜索
        while (!queue.isEmpty()) {
            // 从队列中取出当前树节点，进行下一步搜索
            TreeNode parentNode = queue.poll();

            // 进一步搜索它的所有子节点
            for (TreeNode child : parentNode.children) {
                // BFS找到第一个答案便可以直接返回
                if (child.value == t)
                    return child.number;
                // 将新找到的节点放入队列
                queue.offer(child);
            }
        }

        // 若搜索完毕还未找到答案，说明无解
        return -1;
    }

    // 构建树，返回根节点
    TreeNode buildTree(int[] parents, int[] values) {
        int n = parents.length;
        TreeNode[] tree = new TreeNode[n];
        for (int i = 0; i < n; i++) {
            tree[i] = new TreeNode(i + 1, values[i]);
            int parentNum = parents[i];
            if (parentNum > 0) {
                TreeNode parent = tree[parentNum - 1];
                parent.children.add(tree[i]);
            }
        }
        return tree[0];
    }

    public static void main(String[] args) {
        int[] parents = {-1, 1, 1, 1, 1, 3, 3, 4, 5, 5, 7, 8, 9, 11};
        int[] values = {9, 7, 4, 1, 6, 8, 2, 9, 8, 7, 6, 8, 2, 5};
        TreeSearchSolution sln = new TreeSearchSolution();
        TreeNode root = sln.buildTree(parents, values);
        int treeNum = sln.findNode(root, 8);
        System.out.println("树节点查找答案为: " + treeNum);
    }
}
